The objective of this study is to evaluate the effect of intravenous (IV) Navelbine (vinorelbine tartrate) in combination with IV cisplatin as first or second line therapy for patients with advanced breast cancer on the following measures of efficacy: tumor response rate, duration of response, time to disease progression, and time to treatment failure. The study will also further define the safety and tolerance of IV Navelbine in combination with IV cisplatin.